using System;
using System.Collections.Generic;

namespace LannyPractiseCode.Shu
{
    public class ChainTreeManager
    {
        
        /// <summary>
        /// 将指定节点插入到二叉树中
        /// </summary>
        /// <param name="tree">树的根节点</param>
        /// <param name="node">需要插入的树</param>
        /// <param name="data">父节点</param>
        /// <param name="direction">左右</param>
        /// <typeparam name="T"></typeparam>
        /// <returns></returns>
        public ChainTree<T> BinTreeAddNode<T>(ChainTree<T> tree, ChainTree<T> node, T data, Direction direction)
        {
            if (tree == null)
                return null;
            if (tree.data.Equals(data))
            {
                switch (direction)
                {
                    case Direction.Left:
                        if (tree.left != null)
                            throw new Exception("树的左结点不为空，不能插入。");
                        else
                            tree.left = node;
                        break;
                    case Direction.Right:
                        if (tree.right != null)
                            throw new Exception("树的右结点不为空，不能插入。");
                        else
                            tree.right = node;
                        break;
                }
            }
            BinTreeAddNode(tree.left, node, data, direction);
            BinTreeAddNode(tree.right, node, data, direction);
            return tree;
        }
        //在二叉树中查找指定的key
        public ChainTree<T> BinTreeFind<T>(ChainTree<T> tree, T data)
        {
            if (tree == null)
                return null;
            if (tree.data.Equals(data))
                return tree;

            return BinTreeFind(tree, data);//??这里应该有问题。
        }
        //获取二叉树的深度
        public int BinTreeLen<T>(ChainTree<T> tree)
        {
            int leftLen;
            int rightLen;
            if (tree == null)
                return 0;
            leftLen = BinTreeLen(tree.left); //递归左子树的深度
            rightLen = BinTreeLen(tree.right);//递归右子书的深度
            return leftLen > rightLen ? leftLen : rightLen;
        }
        //二叉树的先序遍历
        public void BinTree_PreOrder<T>(ChainTree<T> tree)
        {
            if (tree == null)
                return;
            Console.WriteLine(tree.data);//先输出根结点
            BinTree_PreOrder(tree.left);//然后遍历左子树
            BinTree_PreOrder(tree.right);//遍历右子树
        }
        //二叉树的中序遍历
        public void BinTree_MidOrder<T>(ChainTree<T> tree)
        {
            if (tree == null)
                return;
            BinTree_MidOrder(tree.left);//先遍历左子树
            Console.WriteLine(tree.data + "\t");//输出结点
            BinTree_MidOrder(tree.right);
        }
        // 二叉树的后序遍历
        public void BinTree_PostOrder<T>(ChainTree<T> tree)
        {
            BinTree_PostOrder(tree.left);//先遍历左子树
            BinTree_PostOrder(tree.right);//在遍历右子树
            Console.WriteLine(tree.data + "\t");//输出结点
        }
        //清除
        public void BinTreeClear<T>(ChainTree<T> tree)
        {
            if (tree == null)
                return;
            BinTreeClear(tree.left);
            BinTreeClear(tree.right);
            tree = null;
        }
    }
}